/****************************************************
作用：排序任意类型的数据(单独指定排序函数)
Author:LysLee
****************************************************/

#define b_type int
#define b_size (sizeof(b_type))


//通过指针交换任意相同类型的两个变量的值
void any_type_swap(void *vp1,void *vp2,int size) {
  b_type *bp1 = vp1, *bp2 = vp2;
  b_type b_temp;
  while(size >= b_size) { //优先使用b_size交换
    b_temp = *bp1;
    *bp1 = *bp2;
    *bp2 = b_temp;  
    bp1++; bp2++;
    size -= b_size;
  }
  char *cp1 = (char*)bp1, *cp2 = (char*)bp2;
  char c_temp;
  while(size > 0) { //交换剩余字节
    c_temp = *cp1;
    *cp1 = *cp2;
    *cp2 = c_temp;
    cp1++; cp2++;
    size--;
  }
}

//整形数据比较函数
int int_cmp(void *vp1,void *vp2) {
  return *(int*)vp1 - *(int*)vp2;
}

//字符数据比较函数
int char_cmp(void *vp1, void *vp2) {
  return *(char*)vp1 - *(char*)vp2;
}


void any_type_qsort(void *base, int size, int n, int (*cmp)(void*,void*)) {
  if (n<2) return; 
  char *cbase = base;
  int i,j;
  for(i=1,j=0;i<n;i++) //把比标杆元素小的移动到[1-j];
    if(cmp(cbase+size*i, cbase) < 0) {  
      j++; //比标杆小的元素个数增加
      if(i!=j) any_type_swap(cbase+size*i, cbase+size*j,size); //如果i!=j则需要交换,以维持[0-j]
    }
  if(j!=0) any_type_swap(cbase, cbase+size*j,size); //确保递归到两个元素时,左边不大于右边
  
  any_type_qsort(cbase, size, j, cmp);
  any_type_qsort(cbase+size*(j+1), size, n-j-1, cmp);

}


/**************以下为测试代码********************
#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>
#include <malloc.h> 
void printarray(int array[],int n) { //测试用
  int i;
  for(i=0;i<n;i++) printf("%d\n",array[i]);
}

void testf(int *array,int n) {
  struct timeval tv;
  gettimeofday(&tv,NULL);
  double start = tv.tv_sec + tv.tv_usec/1000000.0;
  any_type_qsort(array,sizeof(int),n,int_cmp);
  gettimeofday(&tv,NULL);
  double end = tv.tv_sec + tv.tv_usec/1000000.0;
  printf("time:%.6f\n",end-start);
}

int main(void) 
{
  int n = 512000;
  int *array = malloc(sizeof(int)* n);
  srand(time(NULL));
  int i;
  for(i=0;i<n;i++)
    array[i] = rand();

  testf(array,n);
  //printarray(array,n);
  free(array);
}
*******************************************/
